package Arrays;

import java.util.HashSet;
import java.util.Set;

public class _653_TwoSumIVInputisaBST {
    //solution 1:change the BST into array,sort it and solve it as normal find target question
    public boolean findTarget(TreeNode root, int k){
        Set<Integer> sets = new HashSet<Integer>();
        return find(root,k,sets);
    }

    public boolean find(TreeNode root, int k, Set<Integer> sets){
        if(root==null){
            return false;
        }
        if(sets.contains(k-root.val)){
            return true;
        }
        sets.add(root.val);
        return find(root.left,k,sets) || find(root.right,k,sets);
    }
    //solution 2: use the idea that get sum and judge the value and the target,and choose node to down in
    //solution 2:wrong answer,don't take all situation into control
    public boolean findTarget1(TreeNode root, int k) {
        TreeNode p1  = root, p2 = root;
        while((p1.left!=null ||p1.right!=null) || (p2.left!=null || p2.right!=null)){
            int sum = p1.val+p2.val;
            if(sum==k){
                if(p1!=p2) {
                    return true;
                }else{
                    if(p1.left!=null){
                        p1 = p1.left;
                    }else if(p2.right!=null){
                        p2 = p2.right;
                    }else{
                        break;
                    }
                }
            }else if(sum<k){
                if((p1.right!=null) && (p2.right!=null)){
                    if(((p1.right.val+p2.val)-sum)<=((p1.val+p2.right.val)-sum)){
                        p1 = p1.right;
                    }else{
                        p2 = p2.right;
                    }
                }else {
                    if (p1.right != null) {
                        p1 = p1.right;
                    } else if (p2.right != null) {
                        p2 = p2.right;
                    } else {
                        break;
                    }
                }
            }else {
                if ((p1.left != null) && (p2.left != null)) {
                    if((sum-(p1.left.val+p2.val))<=(sum-(p1.val+p2.left.val))){
                        p1 = p1.left;
                    }else{
                        p2 = p2.left;
                    }
                } else {
                    if (p1.left != null) {
                        p1 = p1.left;
                    } else if (p2.left != null) {
                        p2 = p2.left;
                    } else {
                        break;
                    }
                }
            }
        }
        if(p1!=p2 && p1.val+p2.val==k){
            return true;
        }
        return false;
    }
}
